#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/26 16:45
# @USER    : Shengji He
# @File    : RemoveDuplicateNodeLCCI.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:
        """
        Write code to remove duplicates from an unsorted linked list.

        Example1:
            Input: [1, 2, 3, 3, 2, 1]

            Output: [1, 2, 3]
        Example2:
            Input: [1, 1, 1, 1, 2]

            Output: [1, 2]
        Note:
            - The length of the list is within the range[0, 20000].

            - The values of the list elements are within the range [0, 20000].

        Follow Up:
            - How would you solve this problem if a temporary buffer is not allowed?

        :param head:
        :return:
        """
        if not head:
            return head
        ans = ListNode(head.val)
        temp = ans
        tempbuffer = [head.val]
        while head.next:
            if head.next.val not in tempbuffer:
                temp.next = ListNode(head.next.val)
                tempbuffer.append(head.next.val)
                temp = temp.next
            head = head.next
        return ans


if __name__ == '__main__':
    S = Solution()
    nums = [1, 1, 1, 1, 2]
    # nums = [1, 2, 3, 3, 2, 1]
    head = ListNode(nums[0])
    temp = head
    for i in range(1, len(nums)):
        temp.next = ListNode(nums[i])
        temp = temp.next
    output = S.removeDuplicateNodes(head)
    print('done')
